(1) Field of the Invention
The present invention relates to a technology for making it difficult to analyze the program by making the execution order of the instruction blocks configuring the program complex.
(2) Description of the Related Art
Among the programs that operate on a computer, there are programs that cause disadvantages when sets of instruction that performs a certain process and sets of instructions that perform other processes are distinguished. Example of such program is a program including a process for checking tampering. Usually, the program having the tampering checking function includes a set of instructions for performing the tampering check, a set of instructions for performing valid process when no tampering is found, and a set of instructions for performing an exceptional process when tampering is found. In this case, when it is specified where the set of instructions for checking tampering is in the part of the programs, the following problems would arise. More specifically, analyzing the set of instruction for checking tampering with priority and altering the set of instruction so that the tampering check is skipped allows tampering the program such that the valid process is performed regardless of the result of the tampering check.
Furthermore, another example includes a case where information to be kept confidential is included in the program and the information is calculated from a specific set of instructions. Here, the secret information is information that causes some disadvantages to a provider of the program through analysis or alteration. More specifically, the information to be kept confidential includes, for example, a key for decrypting encrypted data, programs other than the program, information used for authenticating the validity of the device itself (the program or the device where the program is executed) with regard to a device other than the device where the program is executed, and information indicating the usage right of contents such as a movie. In this case, when the set of instruction to be kept secret is specified in each set of instructions included in the program, analyzing and altering the set of instructions reveals the information to be kept confidential, or assigning invalid right to an invalid person.
Another example of distinguishing the set of instructions for performing a process and a set of instruction for performing another process is monitoring the sets of instructions that are successively executed. Generally, in a program where no measure has been taken for analysis, the sets of instructions necessary for performing a certain process is successively executed, and the execution result is usually assigned to a specific variable. With this characteristic, it is possible to assume that the part where the specific variable is not used among the sets of instructions that are successively executed is a part where the processes are switched.
In order to avoid such an attack, there is a technique disclosed in Patent Reference 1, for example, which makes the analysis difficult by switching the execution order of the set of instructions which execute processes that are not related each other, and by executing each set of the instructions in the order after the switching. Here, if the same result as the result generated by the original program cannot be obtained due to the switching of the execution order, the original purpose of the program is not achieved. For this reason, the switching of the execution order needs to be performed in a range where it does not affect the execution result of the program.
[Patent Reference 1] Japanese Unexamined Patent Application Publication No. 2000-076064
[Patent Reference 2] International Publication WO2006/001365
However, the switching of the execution order shown in the conventional technology has a problem that the analysis is not fully made difficult in a program which has a complex control configuration including branching and a loop.
FIG. 1 shows an inclusive set of instructions D including the set of instructions for the process 1 and the set of instructions for the process 2. Note that the term “inclusive set of instruction” is used for the set of instructions referring the set of instructions included in the set of instructions.
The problem is described with reference to FIG. 1. The program D on the leftmost part of FIG. 1 includes the first set of instructions executing the process 1 and the second set of instructions executing the process 2. The first set of instructions executing the process 1 includes three blocks, namely, the block A1, the block A2, and the block A3. The set of instructions executing the process 2 includes 6 blocks, namely, the block B1, the block B2 . . . and the block B6. Here, each block is a significant unit including one or more instructions, and is also referred to as an instruction block. Furthermore, for the simplicity of explanation, the process 1 and the process 2 are considered to be processes independent of each other. More specifically, the processes are not in the relationship where one of the blocks in the process 2 cannot be executed unless one of the blocks in the process 1 is executed (or vice versa).
As shown in FIG. 1, in the process 1, correct result can be obtained when each block is executed once in an order from A1, A2, to A3. Furthermore, in the process 2, correct result can be obtained when each block is executed in an order B1, B2 . . . , and the process to go back to B2 after B6 is executed is repeated for a few times.
In this case, when the execution order of the sets of instructions is switched without taking the control configuration of the set of instructions (loop), the blocks among the set of instructions executing the process 1 (the block A1 to the block A3) that are positioned in the loop in the process 2 are executed for multiple times. For example, the block is repeated as many as the number of the times that the loop is repeated. Each set of instructions (block) configuring the process 1 is originally configured to obtain a correct result when it is executed once. Accordingly, when each of the instructions (each block) is executed in such an execution order, the correct result cannot be obtained (for example, see the inclusive set of instructions D1 in the middle of FIG. 1).
On the other hand, when the execution order of each set of instructions (each block) is modified taking into consideration of the control configuration such that the execution result is not affected, there is a limited number of blocks whose execution order can be switched (for example, the inclusive set of instructions D2 on the right of FIG. 1). Thus, the limited switching facilitates separating (distinguishing) the set of instructions configuring the process 1 and the set of instructions configuring the loop in the process 2 (blocks B2 to B6), and it would be difficult to fully prevent the attack by the invalid analyzer.
In view of the foregoing, it is an object of the present invention to provide a processing device and a program which makes the distinction between the instruction block configuring a certain process and the instruction block configuring the other processes even in a program having a complex control configuration difficult, and an obfuscation device which generates a program thereof.